class Number:
    def __init__(self, n):
        s = str(n)
        self.high = int(s[0])
        self.len = len(s)
        self.low = int("".join(s[1:])) if self.len>1 else 0

class Solution(object):
    def count9(self, n):
        if n==0: return 0
        return self.count9(n-1) * 10 + 10**(n-1)

    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=0: return 0
        num = Number(n)
        cnt=0
        if num.high==1:
            cnt += self.count9(num.len-1)
            cnt += num.low+1
            cnt += self.countDigitOne(num.low)
        else:
            cnt += self.count9(num.len-1) * num.high
            cnt += 10**(num.len-1)
            cnt += self.countDigitOne(num.low)
        return cnt

print(Solution().countDigitOne(13))